Computing and communication networks typically include various devices, such as routers, switches or gateways, which transfer or switch data, such as packets, from one or more sources to one or more destinations. The term “packet,” as used herein, may refer to and be used interchangeably with request, message, ping, traffic, data, datagram, or cell; a fragment of a packet, a fragment of a datagram, a fragment of a cell; or another type, arrangement, or packaging of data. A router is a switching device that may receive a packet on a physical media, such as optical fiber, from another router. The router may analyze the packet, to determine its destination, and forward the packet towards its final destination. Multiple routers within one or more networks may handle a packet before the packet reaches its final destination.
A router may include a number of input and output ports from which the router transmits and receives packets. A switching fabric or other transmission medium may be implemented in the router to carry the packets between the ports. Typically, the information is transmitted within the router in discrete quantities, or “cells,” which the router generates by breaking down information packets that the router receives.
One property of the switching fabric is that cells transmitted through the fabric may arrive at a destination in an out-of-order sequence due to the multiple paths that a cell may take. Thus, although a first cell of a packet of information may be transmitted before a second cell, the second cell may be received before the first cell. Further, there may be significant delay between receipt of the first and second cells. A router may reconstruct a data structure, corresponding to the packet information, from data contained in each of the first and second cells. One way to construct the data structure from data in the first and second transmitted cells may be to store the cell that is first-received (e.g., the second cell of the information packet) and to wait for receipt of the other cell (e.g., the first cell). Once both of the first two cells are received, the two cells may be ordered to construct the data structure.
A destination (e.g., a Packet Forwarding Engine (PFE) corresponding to a port of a router) may need to order a large number of cells, for multiple conversations (e.g., data streams, flows of data, etc.). Each conversation may correspond to a different PFE that is a source of cells of the conversation. Cells for each one of the conversations may need to be reordered individually. Each one of the cells of a conversation may be assigned a corresponding sequence number that may be used to reorder the cells. The destination may continue to wait for a cell with a specific sequence number (herein, missing sequence number) before finishing the reordering of the received cells. One or more of the cells may be dropped (lost) while being transmitted through the fabric and may never reach the destination. Other cells may take an unreasonably long time to arrive at the destination.
The destination may implement a unit garbage scheme that allows the destination to treat a cell (herein, missing cell) with the missing sequence number as “dropped” when the missing cell is not received after a predefined period of time (i.e., after a time out has occurred). The destination may reorder the other received cells, without one or more of the missing cell(s), after the one or more of the missing cells are dropped. The unit garbage scheme may work only for one conversation at a time and may drop only a single missing cell at a time. Under the unit garbage scheme, each conversation may have only a single missing cell dropped before the unit garbage scheme inspects all the other conversations for time out. As a result, the input of the cells may be significantly delayed.
In some situations, the destination may fall so far behind in reordering the cells for one of the conversations that the destination may need to utilize bulk garbage collection. For example, the destination may determine that the destination may no longer receive cells for a particular conversation because the destination may no longer store out-of-order cells (or will not be able to store out-of-order cells because of the number of additional cells needed to fill in the missing sequence). The bulk garbage collection may cease (stall) input (receiving) of all new cells for all the different conversations until the particular conversation is cleaned up. The bulk garbage collection may clean up the particular conversation by dropping the cells with the missing sequence numbers for the one particular conversation. The stalling of all input for all the other conversations not being cleaned up may create numerous undesirable events, such as causing problems (e.g., overflow) in the switch fabric.